package com.bascker.algorithm.practice.unionsearch;

/**
 * 并查集模板
 * 
 * 空间复杂度: O(n)
 */
public class Template {

    /**
     * 存储各元素的最顶层根节点
     */
    int[] UNION_FIND;

    /**
     * step1 初始化: 将所有元素的根指向自己本身
     * @param size  元素个数
     */
    final void init(int size) {
        UNION_FIND = new int[size + 1];
        for (int i = 0; i < UNION_FIND.length; i ++) {
            UNION_FIND[i] = i;
        }
    }

    /**
     * step2 查询元素 x 的最顶层根节点, 并进行路径压缩(同一条链路上的节点都指向根节点)
     * @param x  元素x
     * @return
     */
    final int searchRoot(int x) {
        int root = x;
        
        // 循环查找，直到找到 x 的最顶层的根
        while (root != UNION_FIND[root]) {
            root = UNION_FIND[root];
        }

        // 路径压缩: 同一条链的节点都指向最顶层的根
        int tmp;
        while (x != root) {
            tmp = UNION_FIND[x];    // 缓存节点 x 的父节点
            UNION_FIND[x] = root;   // 刷新节点 x 的顶层根节点
            x = tmp;                // x 上移
        }

        return root;
    }


    // step3 合并集合
    final void merge(int x, int y) {
        int rootX = searchRoot(x);
        int rootY = searchRoot(y);

        // 若 2 个节点的顶层根不是一个，说明二者是 2 颗树，则将 x 合并到 y 中：即 x 的顶层根设置为 y 的顶层根节点
        if (rootX != rootY) {
            UNION_FIND[rootX] = rootY;
        }
    }

}
